/*************************************************************************
	> File Name: 001.priority_queue.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/21 11:29:42 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b;\
    b = __temp;\
}

typedef struct {
    int *data;
    int cnt; //队列中的元素个数
    int capacity; //队列容量
} priority_queue;


priority_queue *init(int n) {
    priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
    q->data = (int *)malloc(sizeof(int) * (n + 1)); //从 1 号位开始存数据
    q->cnt = 0;
    q->capacity = n;
    return q;
}

/*
 * 判断堆是否为空
 */
int empty(priority_queue *q) {
    return q->cnt == 0;
}

/*
 * 获取堆顶元素
 */
int top(priority_queue *q) {
    return q->data[1];
}

/*
 * 入堆
 */
int push(priority_queue *q, int val) {
    if (q == NULL) return -1;
    if (q->cnt == q->capacity) return -1;
    q->data[++q->cnt] = val;
    //自下向上调整
    int ind = q->cnt; //插入值的位置
    //比较插入值与其父节点的值
    while (ind >> 1 && q->data[ind] > q->data[ind >> 1]) { //先判断父节点是否存在，然后再比较
        swap(q->data[ind], q->data[ind >> 1]);
        ind >>= 1;
    }
    return 0;
}


/*
 * 出堆
 */
int pop(priority_queue *q) {
    if (q == NULL) return -1;
    if (empty(q)) return -1;
    //堆尾元素放到堆顶
    q->data[1] = q->data[q->cnt--]; 
    //调整元素
    int ind = 1;
    while ((ind << 1) <= q->cnt) { //当前元素还有孩子
        int temp = ind;
        int left = ind << 1; // 2 * ind
        int right = ind << 1 | 1; // 2 * ind + 1
        if (q->data[left] > q->data[temp]) temp = left;
        if (right <= q->cnt && q->data[right] > q->data[temp]) temp = right;
        if (temp == ind) break;
        swap(q->data[temp], q->data[ind]);
        ind = temp;
    }
    return 0;
}

/*
 * 清除堆
 */
void clear(priority_queue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}


int main() {
    srand(time(0));
    #define max_op 20 
    priority_queue *q = init(max_op);
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        push(q, val);
        printf("insert %d to the priority_queue\n", val);
    }

    for (int i = 0; i < max_op; i++) {
        printf("%d ",top(q));
        pop(q);
    }

    printf("\n");
    clear(q);
    #undef max_op

    return 0;
}
